package org.codetranslators.common.optimization;

import org.codetranslators.common.SpanningTreeDFS;
import org.codetranslators.common.SpanningTree;
import org.codetranslators.common.DominatorTreeNode;
import org.codetranslators.common.DominatorTree;
import org.codetranslators.common.TreeNode;
import org.codetranslators.common.DiGraph;
import org.codetranslators.common.Node;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Vector;
import java.util.HashMap;

public abstract class DominatorTreeStrategy {
	
	public abstract DominatorTree getDominatorTree(DiGraph graph, Node startNode);

}

class LengauerTarjan extends DominatorTreeStrategy{
	private HashMap semidominators; 
	private HashMap ancestors;
	private HashMap immediateDominators;
	private HashMap sameDominators;
	private SpanningTreeDFS spanningTreeDFS;
	private SpanningTree spanningTree;
	private Node startNode;
	private DiGraph graph;
	
	public LengauerTarjan(){
		semidominators = new HashMap();
		ancestors = new HashMap();
		immediateDominators = new HashMap();
		sameDominators = new HashMap();
	}
	
	public DominatorTree getDominatorTree(DiGraph graph, Node startNode){
		// Get the spanning tree from the input graph		
		spanningTreeDFS = new SpanningTreeDFS();
		this.graph = graph;
		this.startNode = startNode;
		spanningTree = (SpanningTree)spanningTreeDFS.execute(graph, startNode);
		HashMap semiDomVsNodes = new HashMap();
		
		// Loop through nodes in the graph starting with the highest depth first number and 
		// going backwards through to the root (excluding the root)
		int numNodes = graph.getNumNodes();
		for(int i = numNodes -1; i > 0; i--){
			Node graphNode = spanningTree.getVisitedNode(i);
			Node parent = spanningTree.getParentInTree(graphNode);
			Node semiDominator = parent;    // Initialize the semidominator to the parent
			Node temp = null;
			
			Vector predecessors = graphNode.getPredecessors();
			int numPredecessors = predecessors.size();
			int dfNumOfNode = spanningTree.getDepthFirstNumber(graphNode);
			
			// The following loop calculates the semidominator using the fact that the semidominator is the
			// node with the following properties:
			// 1. If the predecessor is an ancestor of the current node in the spanning tree, it is a candidate
			//    to be the semidominator
			// 2. Else, if it is not an an ancestor, the semidominator of the predecessor with the smallest
			//    depth number
			// 3. The semidominator is the node of the above list with the smallest depth number 
			
			for(int j = 0; j < numPredecessors; j++){
				Node prdNode = (Node)predecessors.elementAt(j);
				int dfNumOfPred = spanningTree.getDepthFirstNumber(prdNode);
				if(dfNumOfPred <= dfNumOfNode)    // Predecessor is an ancestor
					temp = prdNode;
				else                              // Predecessor is an NOT an ancestor
					temp = (Node)semidominators.get(ancestorWithLowestSemi(prdNode));
				
				if(spanningTree.getDepthFirstNumber(temp) <
						spanningTree.getDepthFirstNumber(semiDominator))
					semiDominator = temp;
			}
			
			// Put the semidominator determined above into the semidominator bucket (HashMap)
			semidominators.put(graphNode, semiDominator);
			addToSemiDominatorBucket(semiDomVsNodes, semiDominator, graphNode);
			link(parent, graphNode);
			
			// Calculate the immediate dominator
			Vector childrenOfSemiDominator = (Vector) semiDomVsNodes.get(parent);
			int numChildren = 0;
			if(childrenOfSemiDominator != null)
				numChildren = childrenOfSemiDominator.size();
			
			for(int k = 0; k < numChildren; k++){
				Node child = (Node) childrenOfSemiDominator.elementAt(k);
				Node prevNode = ancestorWithLowestSemi(child);
				if(semidominators.get(prevNode) == semidominators.get(child))
					immediateDominators.put(child, parent);
				else
					sameDominators.put(child, prevNode);
			}
		}
		
		// Deferred dominator calculations
		for(int m = 1; m < numNodes; m++){
			Node node = graph.getNode(m);
			Node sameNode = (Node) sameDominators.get(node);
			if(sameNode != null)
				immediateDominators.put(node, (Node)immediateDominators.get(sameNode));
		}
		
		// Create the dominator tree
		return createDominatorTree();
	}
	
	private Node ancestorWithLowestSemi(Node node){
		Node temp = node;
		while(ancestors.get(node) != null){
			Node semiDomOfNode = (Node) semidominators.get(node);
			Node semiDomOfTempNode = (Node) semidominators.get(temp);
			if(spanningTree.getDepthFirstNumber(semiDomOfNode) <
					spanningTree.getDepthFirstNumber(semiDomOfTempNode))
				temp = node;
			node = (Node) ancestors.get(node);
		}
		return temp;
	}
	
	private void link(Node parent, Node node){
		ancestors.put(node, parent);
	}
	
	private void addToSemiDominatorBucket(HashMap semiDomVsNodes, Node semiDominator, Node graphNode){
		Vector nodes = (Vector)  semiDomVsNodes.get(semiDominator);
		if(nodes == null) nodes = new Vector();
		nodes.addElement(graphNode);
		semiDomVsNodes.put(semiDominator, nodes);
	}
	
	private DominatorTree createDominatorTree(){
		
		// First create the dominator tree nodes
		HashMap nodeVsDominators = new HashMap();
		DominatorTreeNode dominatorTreeRoot = null;
		int numNodes = graph.getNumNodes();
		for(int i = 0; i < numNodes; i++)
		{
			Node node = graph.getNode(i);
			TreeNode treeNode = new TreeNode(node.getName());
			DominatorTreeNode dominatorTreeNode = new DominatorTreeNode(treeNode, node);
			dominatorTreeNode.setName(node.getName());
			if(node == startNode)
				dominatorTreeRoot = dominatorTreeNode;
			nodeVsDominators.put(node, dominatorTreeNode);
		}
		
		// Populate the tree from the immediateDominators HashMap
		Set entries = immediateDominators.entrySet();
		Iterator iter = entries.iterator();
		while(iter.hasNext())
		{
			Map.Entry entry = (Map.Entry) iter.next();
			Node node = (Node)entry.getKey();
			Node domNode = (Node)entry.getValue();
			
			DominatorTreeNode dtNode = (DominatorTreeNode) nodeVsDominators.get(node);
			if(domNode == null){
				// node must have had the starting node as it's immediate dominator
				dominatorTreeRoot.addChild(dtNode);
			}
			else
			{
				DominatorTreeNode dtDomNode = (DominatorTreeNode) nodeVsDominators.get(domNode);
				dtDomNode.addChild(dtNode);
			}
		}
		
		// Create a new dominator tree object, populate it and return it
		DominatorTree dominatorTree = new DominatorTree();
		dominatorTree.setDominatorTreeRoot(dominatorTreeRoot);
		dominatorTree.setGraphNodeVsDominatorTreeNode(nodeVsDominators);
		
		return dominatorTree;
	}
}